package net.tp.algo.heap;

import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.NoSuchElementException;

/**
 * 
 * <p>Interval Heap. Interval Heap is a double-ended priority queue where it allows you to delete both min
 * and max elements.<p>
 * 
 * <p>Interval heap is a complete binary tree where each node contains two elements to create interval $[a, b]$ with $a &le; b$.
 * If the number of elements n is odd, the last node only has one element $a$ (conceptually considered as interval $[a, a]$).
 * If interval $[a, b]$ is parent of $[c, d]$ then $[c, d] &sube; [a, b]$ or $a &le; c &le; d &le; b$.</p>
 * 
 * <p>The interval heap is the combination of min-heap and max-heap. The left elements form a min heap
 * and the right elements form a max heap. If n is odd, the last element can be considered
 * as belonging to either left min heap or right max heap. Array is used to store the elements for interval heap
 * (just like binary heap). Each node covers two elements. Node is only an abstract concept in the implementation.
 * For example, the root node includes {@code element[0]} and {@code element[1]}. The {@code element[i]} belongs to {@code node[i/2]}. For a left {@code element[i]}
 * (i.e. {@code i} is even), the left child index is {@code (i+1)*2}, the parent index is {@code ((i-2)/4)*2}.
 * For a right {@code element[i]}, the left child index is {@code i*2+1}, the parent index is {@code ((i-2)/4)*2+1}.
 * The right child index = the left child index + 2.</p>
 * 
 * <p>The interval heap's operations are very similar to those of binary heap. To <strong>delete the min or max element</strong>,
 * swap the min/max element at the position 0/1 with the last element, then sift the swapped element down.
 * When sifting down, the element must be compared with its sibling and swap if
 * necessary to make sure the interval is valid (i.e. left element &le; right element).
 * To <strong>insert a new element</strong>, append the element to end then sift it up. When sifting up, there is no need
 * to compare the element with its sibling because the interval is always valid.
 * Each operation takes $O(n log(n))$ time. To <strong>make the heap</strong>, fix the intervals first
 * (i.e. left element &le; right element), then go through each element in the backward order and sift it down.
 * Making heap takes $O(n)$ time.</p>
 * 
 * <p>Special care is needed for the last element of the one-element node when sifting up or down because the last element is
 * considered as either belonging to the left min-heap or right max-heap. If $(a, b)$ is the parent of $c$ (which is the last
 * element), then $a &le; c &le; b$. Therefore, when sifting up, if $c &gt; b$, then sift $c$ up in the right max-heap, else 
 * sift it up in the left min-heap. When sifting an element down the right max-heap, consider $c$ as belonging to the max-heap.</p>
 * 
 * @author Trung Phan
 *
 * @param <E> element type
 * @time Construct, add, remove min/max, update priority: $O(n)$. Read: $O(n)$.
 * @space $O(n)$.
 * 
 * @see BinaryHeap
 * @see <a href="http://www.mhhe.com/engcs/compsci/sahni/enrich/c9/interval.pdf">Interval Heaps</a>
 */
public class IntervalHeap<E> {

	private final Comparator<? super E> comparator;
	private E[] elements;
	private int n;

	/**
	 * Create interval-heap.
	 */
	public IntervalHeap() {
		this((Collection<E>)null, null);
	}
	
	/**
	 * Create interval-heap.
	 * @param comparator comparator
	 */
	public IntervalHeap(Comparator<? super E> comparator) {
		this((Collection<E>)null, comparator);
	}
	
	/**
	 * Create interval-heap with predefined elements.
	 * 
     * @param elements initial elements for the heap
	 * @see IntervalHeap#IntervalHeap(Collection, Comparator)
	 */
	public IntervalHeap(Collection<E> elements) {
		this(elements, null);
	}
	
	/**
	 * Create interval-heap with predefined elements.
	 * 
     * @param elements initial elements for the heap
	 * @see IntervalHeap#IntervalHeap(Collection, Comparator)
	 */
	@SafeVarargs
    @SuppressWarnings("varargs")
	public IntervalHeap(E ... elements) {
		this(Arrays.asList(elements), null);
	}
	
	/**
	 * Create interval-heap with predefined elements.
	 * 
     * @param comparator element comparator
     * @param elements initial elements for the heap
	 * @see IntervalHeap#IntervalHeap(Collection, Comparator)
	 */
	@SafeVarargs
    @SuppressWarnings("varargs")
	public IntervalHeap(Comparator<? super E> comparator, E ... elements) {
		this(Arrays.asList(elements), comparator);
	}
	
	/**
	 * Create interval-heap with predefined elements.
	 * 
	 * @time $O(n log(n))$
	 * @space $O(n)$
	 * @param elements nullable. Ignored if null.
	 * @param comparator nullable. If null, elements must be comparable.
	 */
	@SuppressWarnings("unchecked")
	public IntervalHeap(Collection<E> elements, Comparator<? super E> comparator) {
		this.comparator = comparator;
		
		if (elements == null) {
			this.elements = (E[])new Object[16];
		}
		else {
			this.n = elements.size();
			int len = Math.max(16, Integer.highestOneBit(n) * 2);
			
			this.elements = (E[])new Object[len];
			int i = 0;
			for (E element : elements) {
				this.elements[i++] = element;
			}
			
			heapify();
		}
	}
	
	/**
	 * Return true if the heap is empty.
	 * @return true if the heap is empty.
	 * @time $O(1)$
	 */
	public boolean empty() {
		return n == 0;
	}
	
	/**
	 * Size of the heap.
	 * @return size of the heap.
	 * @time $O(1)$
	 */
	public int size() {
		return n;
	}
	
	/**
	 * Add an element into the heap.
	 * 
	 * @time $O(n log(n))$
	 * @param element element to add
	 * @throws NullPointerException if element is null.
	 */
	public void add(E element) {
		
		if (element == null) throw new NullPointerException();
		
		expandArrayIfFull();
		
		n++;
		int i = n-1;
		elements[i] = element;

		i = fixInterval(i);
		siftUp(i);
		
	}
	
	/**
	 * Get minimum element.
	 * 
	 * @time $O(1)$
	 * @return minimum element.
	 * @throws NoSuchElementException if heap is empty.
	 */
	public E min() {
		if (n == 0) throw new NoSuchElementException();

		return elements[0];
	}
	
	/**
	 * Get maximum element.
	 * 
	 * @time $O(1)$
	 * @return maximum element.
	 * @throws NoSuchElementException if heap is empty.
	 */
	public E max() {
		if (n == 0) throw new NoSuchElementException();

		return n > 1 ? elements[1] : elements[0];
	}
	
	/**
	 * Remove the minimum element.
	 * 
	 * @time $O(n log(n))$
	 * @return minimum element.
	 * @throws NoSuchElementException if heap is empty.
	 */
	public E removeMin() {
		if (n == 0) throw new NoSuchElementException();
		
		E result = elements[0];
		swap(0, n-1);
		elements[n-1] = null;
		n--;
		
		if (n > 0) {
			int i = fixInterval(0);
			siftDown(i);
		}
		
		shrinkArrayIfPossible();
		
		return result;
	}
	
	/**
	 * Remove the maximum element.
	 * 
	 * @time $O(n log(n))$
	 * @return maximum element.
	 * @throws NoSuchElementException if heap is empty.
	 */
	public E removeMax() {
		if (n == 0) throw new NoSuchElementException();
		if (n == 1) {
			return removeMin();
		}
		
		E result = elements[1];
		swap(1, n-1);
		elements[n-1] = null;
		n--;
		
		int i = fixInterval(0);
		siftDown(i);

		shrinkArrayIfPossible();
		
		return result;
	}
	
	
	private void heapify() {
		if (n > 0) {
			for (int i = n%2 == 0 ? n-2 : n-1 ; i >= 0; i-=2) {
				fixInterval(i);
			}
			
			for (int i = n/2; i >= 0; i--) {
				siftDown(i);
			}
		}
		
	}

	private int fixInterval(int i) {
		if (i == n-1 && n % 2 == 1) { // single element in the last node.
			return i;
		}
		
		int left = i % 2 == 0 ? i : i - 1;
		int right = left+1;
		if (less(false, elements[right], elements[left])) {
			swap(left, right);
			return i == left ? right : left;
		}
		return i;
	}
	
	private void siftUp(int i) {
		int r = i % 2; // 0 => left, 1 => right
		
		while (i > 1) { // ignore root
			int parent =  ((i - 2) / 4) * 2 + r; // this formula is wrong if i <= 1
			
			if (i == n-1 && n % 2 == 1) {
				// special case where i is not known to be left or right side.
				// handle specially if it turns out to be right side
				if (less(false, elements[parent+1], elements[i])) {
					swap(i, parent+1);
					i = parent+1;
					break;
				}
			}
			
			if (less(r != 0, elements[i], elements[parent])) {
				swap(i, parent);
				i = parent;
			}
			else {
				break;
			}
		}
	}
	
	private void siftDown(int i) {
		int r = i % 2;

		while (true) {

			int child =  r == 0 ? (i + 1) * 2 : i * 2 + 1;
			
			// handle the last one-element node case
			if (n % 2 == 1 && child == n) {
				child = n - 1;
			}
			
			if (child >= n) {
				break;
			}
			
			if (n % 2 == 1 && child + 2 == n && less(true, elements[child+1], elements[child])) { // handle the last one-element node case
				child++;
			}
			else if (child < n - 2 && less(r != 0, elements[child+2], elements[child])) {
				child += 2;
			}
			
			if (less(r!=0, elements[child], elements[i])) {
				swap(i, child);
				i = child;
				fixInterval(i); // this step only exists for siftDown, not siftUp
			}
			else {
				break;
			}
		}
	}
	
	
	private void swap(int i, int j) {
		if (i != j) {
			E v = elements[i];
			elements[i] = elements[j];
			elements[j] = v;
		}
	}
	
	@SuppressWarnings("unchecked")
	private boolean less(boolean reverse, E element1, E element2) {
		int compare = comparator != null ? comparator.compare(element1, element2):
			((Comparable<E>)element1).compareTo(element2);
		
		return reverse ? compare > 0 : compare < 0;
	}

	private void expandArrayIfFull() {
		if (n == elements.length) {
			elements = Arrays.copyOf(elements, n * 2);
		}
	}
	
	private void shrinkArrayIfPossible() {
		if (elements.length > 16 && n < elements.length / 4) {
			int newLen = Math.max(16, Integer.highestOneBit(n) * 2 );
			elements = Arrays.copyOf(elements, newLen);
		}
	}
	
	boolean valid() {
		if (n == 0) {
			return true;
		}
		
		// check each interval
		for (int i = n%2 == 0 ? n-2 : n-3 ; i >= 0; i-=2) {
			if (less(false, elements[i+1], elements[i])) {
				return false;
			}
		}
		
		// check parent child relationship
		for (int i = n-1; i > 1; i--) {
			int r = i % 2; // 0 => left, 1 => right
			
			int parent = ((i - 2) / 4) * 2 + r; // this formula is wrong if i <= 1
			
			if (!less(r != 0, elements[parent], elements[i])) {
				return false;
			}
		}
		
		return true;
	}
}
